package algorithm;

/**
 * 插入排序，预设第一个数值为已经排序好的，
 * 然后从后面的数组中拿第一个数字放到前面已经排序好的数组中，
 * 在放入过程中不停比较，大于该数字的则向后移一位，
 * 直到新数字放入已排序好的数组中之后，仍然是排序好的数组。
 * */
public class InsertSort {

    public static void main(String[] args) {
        int[] ints = {9, 3, 2, 6, 7, 1, 23, 5, 6};
        insertSort(ints);
        for (int i = 0; i < ints.length; i++) {
            System.out.println(ints[i]);
        }

    }

    private static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = key;
        }

    }
}
